Largest rectangle in histogram [Mono Stack, DP]

Time: O(N); Space: O(N); hard

Given N non-negative integers representing the histogram’s bar height where the width of each bar is 1,

find the area of largest rectangle in the histogram.

Example 1:

Input: [2,1,5,6,2,3]

Output: 10

Explanation:

The largest rectangle is shown in the shaded area, which has area = 10 unit.

class Solution1(object):
    def largestRectangleArea(self, height):
        '''
        :type height: List[int]
        :rtype: int
        '''
        increasing, area, i = [], 0, 0
        while i <= len(height):
            if not increasing or (i < len(height) and height[i] > height[increasing[-1]]):
                increasing.append(i)
                i += 1
            else:
                last = increasing.pop()
                if not increasing:
                    area = max(area, height[last] * i)
                else:
                    area = max(area, height[last] * (i - increasing[-1] - 1 ))
        return area

s = Solution1()
height = [2, 1, 5, 6, 2, 3]
assert s.largestRectangleArea(height) == 10
height = [2, 0, 2]
assert s.largestRectangleArea(height) == 2

See also:

https://leetcode.com/problems/largest-rectangle-in-histogram/

https://www.lintcode.com/problem/largest-rectangle-in-histogram